package leo.mystudy.leetcode.nodelist;

import leo.mystudy.leetcode.ListNode;

import java.util.Objects;
import java.util.Stack;

/**
 * @author leo
 * @version 1.0.0
 * @description
 * @create 2022/3/15 17:27
 */
public class GetIntersectionNode {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        Stack<ListNode> stackA = transListNodeToStack(headA);
        Stack<ListNode> stackB = transListNodeToStack(headB);
        ListNode result = null;
        while (!stackA.isEmpty() && !stackB.isEmpty()) {
            ListNode varA = stackA.pop();
            ListNode varB = stackB.pop();
            if (Objects.equals(varA, varB)) {
                result = varA;
            } else {
                break;
            }
        }
        return result;
    }

    private Stack<ListNode> transListNodeToStack(ListNode node) {
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = node;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        return stack;
    }

    public static void main(String[] args) {
        ListNode headA = ListNode.build(new int[]{4, 1, 8, 4, 5});
        ListNode headB = ListNode.build(new int[]{5, 6, 1, 8, 4, 5});
        ListNode intersectionNode = new GetIntersectionNode().getIntersectionNode(headA, headB);
        System.out.println(intersectionNode);
    }
}
